package 动态数组.栈.中缀转后缀;

import 动态数组.栈.ArrayStack;
import 动态数组.线性表.ArrayList;

/**
 * 中缀表达式转后缀表达式
 */
public class InfixToSuffix {
    public static void main(String[] args) {
        String expression = "(10+20/2*3)/2+8";
        String suffix = fixToSuffix(expression);
        System.out.println(suffix);
    }

    public static String fixToSuffix(String expression) {
        ArrayStack<String> optStack = new ArrayStack<>();
        ArrayList<String> suffixList = new ArrayList<>();
        expression = format(expression);
        String[] tokens = expression.split("#");
        for (String token : tokens) {
            if (token.length() == 0){
                continue;
            }else if (isOperator(token)){
                while (true){
                    if (optStack.isEmpty() || "(".equals(optStack.peek())){
                        optStack.push(token);
                        break;
                    }
                    if (priority(token) > priority(optStack.peek())){
                        optStack.push(token);
                        break;
                    }
                    //优先级小的话就循环添加，并弹出操作符
                    suffixList.add(optStack.pop());
                }

            }else if (isNumber(token)){
                suffixList.add(token);
            }else if ("(".equals(token)){
                optStack.push(token);
            }else if (")".equals(token)){
                while (!"(".equals(optStack.peek())){
                    suffixList.add(optStack.pop());
                }
                optStack.pop();
            }
        }
        while (!optStack.isEmpty()){
            suffixList.add(optStack.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (String s : suffixList) {
            sb.append(s);
            sb.append(" ");
        }
        return sb.toString();
    }

    private static boolean isNumber(String token) {
        return token.matches("\\d+");
    }

    private static int priority(String token) {
        if ("*".equals(token) || "/".equals(token)){
            return 1;
        }else if ("+".equals(token) || "-".equals(token)){
            return 0;
        }else {
            throw new IllegalArgumentException("wrong expression!");
        }
    }

    private static boolean isOperator(String token) {
        //对象.equals("_")对象可能为空，建议"_".equals(对象)
        return "+".equals(token) || "-".equals(token)  || "*".equals(token) || "/".equals(token);
    }

    public static String format(String expression){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            //如果仅过滤数字的话，不会过滤如下情况："(10+20/2*3)(1+2)/2+8"，会使数字栈有两个数字bottom [40,9] top，
            //会将两个括号中的内容分别进行一个计算，因此要写全
            char c = expression.charAt(i);
            if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/'){
                sb.append('#');
                sb.append(c);
                sb.append('#');
            }else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
